/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    /**
     * 1,2,3,4,5,
     *
     *  1
     *    2
     *      3
     *         4
     *            5
     *               null 0
     *             5
     *          4 delete
     *        3
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        removeNthFromEnd2(dummy, n);
        return dummy.next;
    }

    public int removeNthFromEnd2(ListNode head, int n) {
        if (head == null) {
            return 0;
        }
        int count = removeNthFromEnd2(head.next, n) + 1;
        if ((count - 1) == n) {
            head.next = head.next.next;
        }
        System.out.println(head.val + "  " + count);
        return count;
    }

    public static void main(String[] args) {
        int[] array = {1};
        ListNode head = new ListNode(array[0]);
        ListNode pre = head;
        for (int i = 1; i < array.length; i++) {
            ListNode listNode = new ListNode(array[i]);
            pre.next = listNode;
            pre = listNode;
        }
        Solution solution = new Solution();
        ListNode listNode = solution.removeNthFromEnd(head, 1);

        System.out.println("  " );
    }

    // 本算法使用递归实现，一趟扫描完成需求开发，建议使用双指针。
}